//
// Created by wlk12 on 2024/6/13.
//
#include "binary_tree_tool.h"
#include <deque>
#include <vector>

void levelOrder(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    std::deque<TreeNode*> nodes;
    nodes.push_back(root);
    while (!nodes.empty())
    {
        auto node = nodes.front();
        nodes.pop_front();
        std::cout << node->value << ", ";
        if (node->left != nullptr)
        {
            nodes.push_back(node->left);
        }
        if (node->right != nullptr)
        {
            nodes.push_back(node->right);
        }
    }
}

void zOrder(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }

    std::deque<TreeNode*> nodes;
    nodes.push_back(root);

    bool isLeft = true;
    while (!nodes.empty())
    {
        auto levelCount = nodes.size();
        if (isLeft)
        {
            for (int i = 0; i < levelCount; ++i)
            {
                auto node = nodes.back();
                nodes.pop_back();
                std::cout << node->value << ", ";
                if (node->left != nullptr)
                {
                    nodes.push_front(node->left);
                }
                if (node->right != nullptr)
                {
                    nodes.push_front(node->right);
                }
            }
        }
        else
        {
            for (int i = 0; i < levelCount; ++i)
            {
                auto node = nodes.front();
                nodes.pop_front();
                std::cout << node->value << ", ";
                if (node->right != nullptr)
                {
                    nodes.push_back(node->right);
                }
                if (node->left != nullptr)
                {
                    nodes.push_back(node->left);
                }
            }
        }
        isLeft = !isLeft;
    }
}

void zOrder2(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }

    std::vector<TreeNode*> queues[2];
    int current = 0;
    int next = 1;
    queues[current].push_back(root);
    while (!queues[current].empty())
    {
        for (int i = (int)queues[current].size() - 1; i  >= 0; --i)
        {
            auto node = queues[current][i];
            std::cout << node->value << ", ";
            if (next == 1)
            {
                if (node->left != nullptr)
                {
                    queues[next].push_back(node->left);
                }
                if (node->right != nullptr)
                {
                    queues[next].push_back(node->right);
                }
            }
            else
            {
                if (node->right != nullptr)
                {
                    queues[next].push_back(node->right);
                }
                if (node->left != nullptr)
                {
                    queues[next].push_back(node->left);
                }
            }
        }
        queues[current].clear();
        current = next;
        next = (next + 1) % 2;
    }
}

void zOrder3(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }

    std::deque<TreeNode*> queue;
    queue.push_back(root);
    std::vector<TreeNode*> layer;
    bool isLeft = true;
    while (!queue.empty())
    {
        layer.clear();
        int count = static_cast<int>(queue.size());
        for (int i = 0; i < count; ++i)
        {
            auto node = queue.front();
            queue.pop_front();
            layer.push_back(node);
            if (node->left)
            {
                queue.push_back(node->left);
            }
            if (node->right)
            {
                queue.push_back(node->right);
            }
        }

        if (!isLeft)
        {
            std::reverse(layer.begin(), layer.end());
        }
        for (auto node : layer)
        {
            std::cout << node->value << ", ";
        }
        isLeft = !isLeft;
    }
    std::cout << std::endl;

}

int main()
{
    std::vector<int> nums{1, 2, 3, -1, 5, 8, 9, -1, -1, 10, 11, 12, 13};
    auto bt = createTree(nums);
    printTree(bt);

    std::cout << "Level Order: ";
    levelOrder(bt);
    std::cout << std::endl;

    std::cout << "Z Order : ";
    zOrder(bt);
    std::cout << std::endl;

    std::cout << "Z Order2: ";
    zOrder2(bt);
    std::cout << std::endl;

    std::cout << "Z Order3: ";
    zOrder3(bt);
    std::cout << std::endl;

    deleteTree(bt);

    return 0;
}